{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Nodes Into the Maximum Number of Groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: magnificentSets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将节点分成尽可能多的组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>n</code>&nbsp;，表示一个 <strong>无向</strong>&nbsp;图中的节点数目，节点编号从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i, </sub>b<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code><sub>&nbsp;</sub>之间有一条&nbsp;<strong>双向</strong>&nbsp;边。注意给定的图可能是不连通的。</p>\n",
    "\n",
    "<p>请你将图划分为&nbsp;<code>m</code>&nbsp;个组（编号从 <strong>1</strong>&nbsp;开始），满足以下要求：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>图中每个节点都只属于一个组。</li>\n",
    "\t<li>图中每条边连接的两个点&nbsp;<code>[a<sub>i, </sub>b<sub>i</sub>]</code>&nbsp;，如果&nbsp;<code>a<sub>i</sub></code>&nbsp;属于编号为&nbsp;<code>x</code>&nbsp;的组，<code>b<sub>i</sub></code>&nbsp;属于编号为&nbsp;<code>y</code>&nbsp;的组，那么&nbsp;<code>|y - x| = 1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回最多可以将节点分为多少个组（也就是最大的<em>&nbsp;</em><code>m</code>&nbsp;）。如果没办法在给定条件下分组，请你返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/13/example1.png\" style=\"width: 352px; height: 201px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>如上图所示，\n",
    "- 节点 5 在第一个组。\n",
    "- 节点 1 在第二个组。\n",
    "- 节点 2 和节点 4 在第三个组。\n",
    "- 节点 3 和节点 6 在第四个组。\n",
    "所有边都满足题目要求。\n",
    "如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3, edges = [[1,2],[2,3],[3,1]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。\n",
    "没有任何符合题目要求的分组方式。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>两个点之间至多只有一条边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-nodes-into-the-maximum-number-of-groups](https://leetcode.cn/problems/divide-nodes-into-the-maximum-number-of-groups/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-nodes-into-the-maximum-number-of-groups](https://leetcode.cn/problems/divide-nodes-into-the-maximum-number-of-groups/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]', '3\\n[[1,2],[2,3],[3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        G = [[] for _ in range(n+1)]\n",
    "        fa = list(range(n+1))\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "            fa[find(a)] = find(b)\n",
    "        for i in range(n+1):\n",
    "            find(i)\n",
    "\n",
    "        def bfs(i):\n",
    "            q = deque([i])\n",
    "            d = {i:1}\n",
    "            while q:\n",
    "                j = q.popleft()\n",
    "                for k in G[j]:\n",
    "                    if k not in d:\n",
    "                        d[k] = d[j] + 1\n",
    "                        q.append(k)\n",
    "                    elif abs(d[k] - d[j]) != 1:\n",
    "                        return -1\n",
    "            return max(d.values())\n",
    "\n",
    "        g = defaultdict(int)\n",
    "        for i in range(1, n+1):\n",
    "            if (x := bfs(i)) == -1:\n",
    "                return -1\n",
    "            g[fa[i]] = max(g[fa[i]], x)\n",
    "        return sum(g.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 1. build adjacency list for undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        # 2. build union find disjoint set for this graph\n",
    "        UF = UnionFind(n)\n",
    "        for u in range(n):\n",
    "            for v in g[u]:\n",
    "                UF.unionSet(u, v)\n",
    "        \n",
    "        # find root of disjoint set for each vertex in the graph\n",
    "        hashmap = defaultdict(list)         # key: root index, value: vertices in the disjoint set rooted at root\n",
    "        for u in range(n):\n",
    "            root = UF.findSet(u)\n",
    "            hashmap[root].append(u)\n",
    "        \n",
    "        # 3. for each disjoint set, if it isn't a bipartite, impossible to divide\n",
    "        ans = 0\n",
    "        for root, nodes in hashmap.items():\n",
    "            if not self.isBipartite(nodes, g):\n",
    "                return -1\n",
    "            else:\n",
    "                ans += self.bfs(nodes, g)\n",
    "        return ans \n",
    "\n",
    "    def bfs(self, nodes: List[int], graph: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        return max depth of disjoint set\n",
    "        nodes: all the vertices in the disjoint set\n",
    "        graph: adjacency list\n",
    "        \"\"\"\n",
    "        n = len(graph)\n",
    "        maxdepth = 0\n",
    "\n",
    "        for start in nodes:\n",
    "            depth = 0\n",
    "            queue = deque([start])\n",
    "            visited = [False] * n\n",
    "            visited[start] = True \n",
    "            while queue:\n",
    "                depth += 1 \n",
    "                for _ in range(len(queue)):\n",
    "                    u = queue.popleft()\n",
    "                    for v in graph[u]:\n",
    "                        if not visited[v]:\n",
    "                            queue.append(v)\n",
    "                            visited[v] = True \n",
    "            maxdepth = max(maxdepth, depth)\n",
    "        \n",
    "        return maxdepth\n",
    "\n",
    "\n",
    "    def isBipartite(self, nodes: List[int], graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UF = UnionFind(n)\n",
    "        for i in nodes:\n",
    "            for j in range(len(graph[i])-1):\n",
    "                if UF.isSameSet(i, graph[i][j]):\n",
    "                    return False \n",
    "                else:\n",
    "                    UF.unionSet(graph[i][j], graph[i][j+1])\n",
    "        return True \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "        \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parents = list(range(n+1))\n",
    "        def getParents(x):\n",
    "            stack = []\n",
    "            while parents[x] != x:\n",
    "                stack.append(x)\n",
    "                x = parents[x]\n",
    "            for y in stack:\n",
    "                parents[y] = x\n",
    "            return x\n",
    "        nexts = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            nexts[a].append(b)\n",
    "            nexts[b].append(a)\n",
    "            ma, mb = getParents(a), getParents(b)\n",
    "            if ma == mb: continue\n",
    "            ma, mb = min(ma, mb), max(ma, mb)\n",
    "            parents[mb] = ma\n",
    "        groups = defaultdict(list)\n",
    "        for i in range(1, n+1):\n",
    "            groups[getParents(i)].append(i)\n",
    "        depths = [-1]*(n+1)\n",
    "        res = 0\n",
    "        q = deque()\n",
    "        for lst in groups.values():\n",
    "            mul = -1\n",
    "            _max = 0\n",
    "            for i in lst:\n",
    "                mul *= -1\n",
    "                depths[i] = mul\n",
    "                q.append((i, 1))\n",
    "                while q:\n",
    "                    i, level = q.popleft()\n",
    "                    for j in nexts[i]:\n",
    "                        if depths[j]*mul > 0: \n",
    "                            if (depths[j]*mul) & 1 != (level+1)&1: return -1\n",
    "                            continue\n",
    "                        depths[j] = (level+1)*mul\n",
    "                        q.append((j, level+1))\n",
    "                _max = max(_max, level)\n",
    "            res += _max \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        \n",
    "        def bfs(ni):\n",
    "            q = deque([ni])\n",
    "            cnt = 1\n",
    "            seen.add(ni)\n",
    "            while q:\n",
    "                node = q.popleft()\n",
    "                if fa[node] == 0:\n",
    "                    fa[node] = ni\n",
    "                # seen.add(node)\n",
    "                for ne in e[node]:\n",
    "                    if depth[ne]:\n",
    "                        if abs(depth[ne] - depth[node]) != 1:\n",
    "                            return -1\n",
    "                    else:\n",
    "                        depth[ne] = depth[node] + 1\n",
    "                        cnt = max(depth[ne], cnt)\n",
    "                    if ne not in seen:\n",
    "                        seen.add(ne)\n",
    "                        q.append(ne)\n",
    "            return cnt\n",
    "     \n",
    "        ans = -1\n",
    "        fa = [0] * (n + 1)\n",
    "        seen = set()\n",
    "        su = 0\n",
    "        d = dict()\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            depth = [0] * (n + 1)\n",
    "            depth[i] = 1\n",
    "            seen = set()\n",
    "            if fa[i] == 0:\n",
    "                tmp = bfs(i)\n",
    "                if tmp == -1:\n",
    "                    return -1\n",
    "                d[i] = tmp\n",
    "                # print(d)\n",
    "            else:\n",
    "                # print(d, fa[i])\n",
    "                tmp = bfs(i)\n",
    "                d[fa[i]] = max(tmp, d[fa[i]])\n",
    "        # print(d)\n",
    "        return sum(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @ staticmethod\n",
    "    def myFind(parent, i):\n",
    "        if parent[i] != i: \n",
    "            parent[i] = Solution.myFind(parent, parent[i])\n",
    "        return parent[i]\n",
    "\n",
    "    @ staticmethod\n",
    "    def myUnion(parent, rank, i, j):\n",
    "        pi, pj = Solution.myFind(parent, i), Solution.myFind(parent, j)\n",
    "        if pi == pj: return\n",
    "        if rank[pi] > rank[pj]:\n",
    "            parent[pj] = pi\n",
    "        elif rank[pi] < rank[pj]:\n",
    "            parent[pi] = pj\n",
    "        else:\n",
    "            parent[pj] = pi\n",
    "            rank[pi] += 1\n",
    "        return\n",
    "\n",
    "    @ staticmethod\n",
    "    def bfs(neighbors, i):\n",
    "        n = len(neighbors)\n",
    "        visited = [n + 1] * n\n",
    "        ans = 0\n",
    "        q = deque([i])\n",
    "        visited[i] = 1\n",
    "        while len(q) > 0:\n",
    "            ans += 1\n",
    "            lq = len(q)\n",
    "            for _ in range(lq):\n",
    "                i = q.popleft()\n",
    "                for j in neighbors[i]:\n",
    "                    if visited[j] == ans:\n",
    "                        return -1\n",
    "                    elif visited[j] < ans or visited[j] == ans + 1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        visited[j] = ans + 1\n",
    "                        q.append(j)\n",
    "        return ans\n",
    "\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent, rank = list(range(n)), [0] * n\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in edges: \n",
    "            i = i - 1\n",
    "            j = j - 1\n",
    "            neighbors[i].append(j)\n",
    "            neighbors[j].append(i)\n",
    "            Solution.myUnion(parent, rank, i, j)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            pi = Solution.myFind(parent, i)\n",
    "            if pi not in d: d[pi] = []\n",
    "            d[pi].append(i)\n",
    "        ans = 0\n",
    "        for key in d:\n",
    "            maxl = 0\n",
    "            for i in d[key]:\n",
    "                il = Solution.bfs(neighbors, i)\n",
    "                if il == -1: return -1\n",
    "                maxl = max(maxl, il)\n",
    "            ans += maxl\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        pa, pb = self.find(a), self.find(b)\n",
    "        if pa != pb:\n",
    "            if self.size[pa] >= self.size[pb]:\n",
    "                self.size[pa] += self.size[pb]\n",
    "                self.p[pb] = pa\n",
    "            else:\n",
    "                self.size[pb] += self.size[pa]\n",
    "                self.p[pa] = pb\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u - 1].append(v - 1)\n",
    "            g[v - 1].append(u - 1)\n",
    "            uf.union(u - 1, v - 1)\n",
    "        mx = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            res = [0] * n\n",
    "            res[i] = 1\n",
    "            tmp = 1\n",
    "            dq = deque([i])\n",
    "            while dq:\n",
    "                tmp += 1\n",
    "                for _ in range(len(dq)):\n",
    "                    a = dq.popleft()\n",
    "                    for nxt in g[a]:\n",
    "                        if res[nxt] == 0:\n",
    "                            res[nxt] = tmp \n",
    "                            dq.append(nxt)\n",
    "            for u, v in edges:\n",
    "                if res[u - 1] and res[v - 1] and res[u - 1] == res[v - 1]:\n",
    "                    return -1\n",
    "            ori = uf.find(i)\n",
    "            mx[ori] = max(mx[ori], tmp - 1)\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            ori = uf.find(i)\n",
    "            if ori in vis:\n",
    "                continue\n",
    "            ans += mx[ori]\n",
    "            vis.add(ori)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        time = [0] * n  # 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）\n",
    "        clock = 0\n",
    "        def bfs(start: int) -> int:  # 返回从 start 出发的最大深度\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:  # 没有在同一次 BFS 中访问过\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1  # 如果不是二分图（有奇环），则无法分组\n",
    "            # 否则一定可以分组\n",
    "            ans += max(bfs(x) for x in nodes)  # 枚举连通块的每个点，作为起点 BFS，求最大深度\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)] # graph[0] is useless\n",
    "        for e in edges:\n",
    "            s, l = e[0], e[1]\n",
    "            graph[s].append(l)\n",
    "            graph[l].append(s)\n",
    "        # print(graph)\n",
    "        # print(nodes, vis)\n",
    "\n",
    "        self.i = 0 # debug\n",
    "        maxDepths = [0] * (n + 1)\n",
    "        for node in range(1, n+1):\n",
    "            minNode, maxDepth = self.bfs(node, n, graph)\n",
    "            if maxDepth == -1:\n",
    "                return -1\n",
    "            maxDepths[minNode] = max(maxDepths[minNode], maxDepth)\n",
    "        return sum(maxDepths)\n",
    "\n",
    "    # TODO optimization: root should have the min degree\n",
    "    def bfs(self, root, n, graph):\n",
    "        vis = [False] * (n + 1)\n",
    "        # print(self.i, 'root:', root, 'degree:', len(graph[root]))\n",
    "        self.i += 1\n",
    "        depths = [0] * (n + 1)\n",
    "        queue = [(root, 1)]\n",
    "        head, tail = 0, 1\n",
    "        minNode, maxDepth = n + 1, 0\n",
    "        while head < len(queue):\n",
    "            cur, depth = queue[head]\n",
    "            # test odd circle\n",
    "            if depths[cur] > 0 and depths[cur] != depth:\n",
    "                return 0, -1\n",
    "            if not vis[cur]:\n",
    "                depths[cur] = depth\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "                minNode = min(minNode, cur)\n",
    "                # print('cur:', cur, depth, 'maxDepth:', maxDepth)\n",
    "                vis[cur] = True\n",
    "                newDepth = depth + 1\n",
    "                for n in graph[cur]:\n",
    "                    if not vis[n]:\n",
    "                        queue.append((n, newDepth))\n",
    "            head += 1\n",
    "\n",
    "        return minNode, maxDepth\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        # 良久之后的重写，还真过了~\r\n",
    "        nxt = [[] for _ in range(n)]\r\n",
    "        parent = [i for i in range(n)]\r\n",
    "\r\n",
    "        def find(x):\r\n",
    "            if parent[x] != x:\r\n",
    "                parent[x] = find(parent[x])\r\n",
    "            return parent[x]\r\n",
    "\r\n",
    "        for u, v in edges:\r\n",
    "            u, v = u - 1, v - 1\r\n",
    "            r0, r1 = find(u), find(v)\r\n",
    "            if r0 != r1:\r\n",
    "                parent[r1] = r0\r\n",
    "            nxt[u].append(v)\r\n",
    "            nxt[v].append(u)\r\n",
    "        group = defaultdict(list)\r\n",
    "        for i in range(n):\r\n",
    "            group[find(i)].append(i)\r\n",
    "        ans = 0\r\n",
    "\r\n",
    "        def min_group(lst):\r\n",
    "            ret = -1\r\n",
    "            for s in lst:\r\n",
    "                ll = 0\r\n",
    "                vis = defaultdict(lambda: -1)\r\n",
    "                q = [[s, -1]]\r\n",
    "                vis[s] = 0\r\n",
    "                b = False\r\n",
    "                while q and not b:\r\n",
    "                    t = []\r\n",
    "                    for v, fa in q:\r\n",
    "                        for nx in nxt[v]:\r\n",
    "                            if fa == nx: continue\r\n",
    "                            if 0 <= vis[nx]:\r\n",
    "                                if vis[nx] == ll:\r\n",
    "                                    ll = -1\r\n",
    "                                    b = True\r\n",
    "                                    break\r\n",
    "                                else:\r\n",
    "                                    continue\r\n",
    "                            vis[nx] = ll + 1\r\n",
    "                            t.append([nx, v])\r\n",
    "                        if b: break\r\n",
    "                    if b: break\r\n",
    "                    q = t\r\n",
    "                    ll += 1\r\n",
    "                ret = max(ret, ll)\r\n",
    "            return ret\r\n",
    "\r\n",
    "        for lst in group.values():\r\n",
    "            v = min_group(lst)\r\n",
    "            if v == -1:\r\n",
    "                return -1\r\n",
    "            ans += v\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "跑一遍bfs后，检查是否是二分图\n",
    "'''\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        time=[0]*n  #判断一个点是否vis\n",
    "        clock=0\n",
    "        def bfs(start:int)->int:  #返回从start出发的最大深度\n",
    "            depth=0\n",
    "            nonlocal clock\n",
    "            clock+=1\n",
    "            time[start]=clock\n",
    "            q=[start]\n",
    "            while q:\n",
    "                tmp=q#创建一个tmp，同时将这一层的q清空\n",
    "                q=[]\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y]!=clock:\n",
    "                            time[y]=clock\n",
    "                            q.append(y)\n",
    "                depth+=1\n",
    "            return depth\n",
    "\n",
    "        color=[0]*n\n",
    "        def is_bipartite(x:int,c:int)->bool:  #二分图判定写法，神奇的dfs\n",
    "            nodes.append(x)\n",
    "            color[x]=c  \n",
    "            for y in g[x]:\n",
    "                if color[y]==c or color[y]==0 and not is_bipartite(y,-c):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans=0\n",
    "        for i,c in enumerate(color):\n",
    "            if c:continue\n",
    "            nodes=[]\n",
    "            if not is_bipartite(i,1): return -1\n",
    "            ans+=max(bfs(x) for x in nodes)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)] # graph[0] is useless\n",
    "        for e in edges:\n",
    "            s, l = e[0], e[1]\n",
    "            graph[s].append(l)\n",
    "            graph[l].append(s)\n",
    "        # print(graph)\n",
    "        # print(nodes, vis)\n",
    "\n",
    "        self.i = 0 # debug\n",
    "        maxDepths = [0] * (n + 1)\n",
    "        for node in range(1, n+1):\n",
    "            minNode, maxDepth = self.bfs(node, n, graph)\n",
    "            if maxDepth == -1:\n",
    "                return -1\n",
    "            maxDepths[minNode] = max(maxDepths[minNode], maxDepth)\n",
    "        return sum(maxDepths)\n",
    "\n",
    "    # root should has the min degree\n",
    "    def bfs(self, root, n, graph):\n",
    "        vis = [False] * (n + 1)\n",
    "        # print(self.i, 'root:', root, 'degree:', len(graph[root]))\n",
    "        self.i += 1\n",
    "        depths = [0] * (n + 1)\n",
    "        queue = [(root, 1)]\n",
    "        head, tail = 0, 1\n",
    "        minNode, maxDepth = n + 1, 0\n",
    "        while head < len(queue):\n",
    "            cur, depth = queue[head]\n",
    "            # test odd circle\n",
    "            if depths[cur] > 0 and depths[cur] != depth:\n",
    "                return 0, -1\n",
    "            if not vis[cur]:\n",
    "                depths[cur] = depth\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "                minNode = min(minNode, cur)\n",
    "                # print('cur:', cur, depth, 'maxDepth:', maxDepth)\n",
    "                vis[cur] = True\n",
    "                newDepth = depth + 1\n",
    "                for n in graph[cur]:\n",
    "                    if not vis[n]:\n",
    "                        queue.append((n, newDepth))\n",
    "            head += 1\n",
    "\n",
    "        return minNode, maxDepth\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a-1].append(b-1)\n",
    "            g[b-1].append(a-1)\n",
    "        \n",
    "        time = [0] * n \n",
    "        clock = 0\n",
    "        def bfs(i):\n",
    "            mx = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[i] = clock\n",
    "            q = deque([(i, base)])\n",
    "            while q:\n",
    "                x, id = q.popleft()\n",
    "                mx = max(mx, id)\n",
    "                for y in g[x]:\n",
    "                    if time[y] != clock:\n",
    "                        time[y] = clock\n",
    "                        q.append((y, id + 1))\n",
    "            return mx\n",
    "\n",
    "        color = [0] * n\n",
    "        def dfs(x, c):\n",
    "            color[x] = c\n",
    "            nodes.append(x) \n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not dfs(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c:\n",
    "                continue\n",
    "            nodes = []\n",
    "            if not dfs(i, 1):\n",
    "                return -1\n",
    "            base = ans + 1\n",
    "            for x in nodes:\n",
    "                ans = max(ans, bfs(x))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        #图的构建\n",
    "        g =[[] for _ in range(n)]\n",
    "        for e1, e2 in edges:\n",
    "            g[e1-1].append(e2-1)\n",
    "            g[e2-1].append(e1-1)\n",
    "        \n",
    "        #判断二分图\n",
    "        def is_bir_map(node,color) -> bool:\n",
    "            nonlocal colors\n",
    "            nonlocal nodes\n",
    "            nodes.append(node)\n",
    "\n",
    "            colors[node] = color\n",
    "\n",
    "            for nei in g[node]:\n",
    "                if colors[nei] == color or colors[nei] == 0 and not is_bir_map(nei, -color):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        visit_time = [0] * n\n",
    "        clock = 0\n",
    "        # bfs求最大深度\n",
    "        def bfs(node)->int:\n",
    "            nonlocal clock\n",
    "            max_deep = 0\n",
    "            clock += 1\n",
    "            visit_time[node] = clock\n",
    "            queue = [node]\n",
    "            while queue:\n",
    "                tmp = queue\n",
    "                queue = []\n",
    "                for son in tmp:\n",
    "                    for nei in g[son]:\n",
    "                        if visit_time[nei] != clock:\n",
    "                            visit_time[nei] = clock\n",
    "                            queue.append(nei)\n",
    "                max_deep += 1\n",
    "            return max_deep\n",
    "\n",
    "\n",
    "        colors = [0] * n\n",
    "        ans = 0\n",
    "        for i,node in enumerate(colors):\n",
    "            if colors[i] != 0:\n",
    "                continue\n",
    "            nodes = []\n",
    "            if not is_bir_map(i,1):\n",
    "                return -1\n",
    "            # 二分图的情况下进行bfs求深度\n",
    "            ans += max(bfs(i) for i in nodes)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        time = [0] * n\n",
    "        clock = 0\n",
    "        def bfs(start):\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1  # 如果不是二分图（有奇环），则无法分组\n",
    "            # 否则一定可以分组\n",
    "            ans += max(bfs(x) for x in nodes)  # 枚举连通块的每个点，作为起点 BFS，求最大深度\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        time = [0] * n \n",
    "        clock = 0\n",
    "\n",
    "        def bfs(start): \n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "        \n",
    "        color = [0] * n\n",
    "        def is_bipartite(x, c):\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1):return -1\n",
    "            ans += max(bfs(x) for x in nodes)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)] # graph[0] is useless\n",
    "        for e in edges:\n",
    "            s, l = e[0], e[1]\n",
    "            graph[s].append(l)\n",
    "            graph[l].append(s)\n",
    "        # print(graph)\n",
    "        # print(nodes, vis)\n",
    "\n",
    "        self.i = 0 # debug\n",
    "        maxDepths = [0] * (n + 1)\n",
    "        for node in range(1, n+1):\n",
    "            minNode, maxDepth = self.bfs(node, n, graph)\n",
    "            if maxDepth == -1:\n",
    "                return -1\n",
    "            maxDepths[minNode] = max(maxDepths[minNode], maxDepth)\n",
    "        return sum(maxDepths)\n",
    "\n",
    "    def bfs(self, root, n, graph):\n",
    "        vis = [False] * (n + 1)\n",
    "        # print(self.i, 'root:', root, 'degree:', len(graph[root]))\n",
    "        self.i += 1\n",
    "        depths = [0] * (n + 1)\n",
    "        queue = [(root, 1)]\n",
    "        head, tail = 0, 1\n",
    "        minNode, maxDepth = n + 1, 0\n",
    "        while head < len(queue):\n",
    "            cur, depth = queue[head]\n",
    "            # test odd circle\n",
    "            if depths[cur] > 0 and depths[cur] != depth:\n",
    "                return 0, -1\n",
    "            if not vis[cur]:\n",
    "                depths[cur] = depth\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "                minNode = min(minNode, cur)\n",
    "                # print('cur:', cur, depth, 'maxDepth:', maxDepth)\n",
    "                vis[cur] = True\n",
    "                newDepth = depth + 1\n",
    "                for n in graph[cur]:\n",
    "                    if not vis[n]:\n",
    "                        queue.append((n, newDepth))\n",
    "            head += 1\n",
    "\n",
    "        return minNode, maxDepth\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n+1)] # graph[0] is useless\n",
    "        for e in edges:\n",
    "            s, l = e[0], e[1]\n",
    "            graph[s].append(l)\n",
    "            graph[l].append(s)\n",
    "        # print(graph)\n",
    "        # print(nodes, vis)\n",
    "\n",
    "        self.i = 0 # debug\n",
    "        maxDepths = [0] * (n + 1)\n",
    "        for node in range(1, n+1):\n",
    "            minNode, maxDepth = self.bfs(node, n, graph)\n",
    "            if maxDepth == -1:\n",
    "                return -1\n",
    "            maxDepths[minNode] = max(maxDepths[minNode], maxDepth)\n",
    "        return sum(maxDepths)\n",
    "\n",
    "    # root should have the min degree\n",
    "    def bfs(self, root, n, graph):\n",
    "        vis = [False] * (n + 1)\n",
    "        # print(self.i, 'root:', root, 'degree:', len(graph[root]))\n",
    "        self.i += 1\n",
    "        depths = [0] * (n + 1)\n",
    "        queue = [(root, 1)]\n",
    "        head, tail = 0, 1\n",
    "        minNode, maxDepth = n + 1, 0\n",
    "        while head < len(queue):\n",
    "            cur, depth = queue[head]\n",
    "            # test odd circle\n",
    "            if depths[cur] > 0 and depths[cur] != depth:\n",
    "                return 0, -1\n",
    "            if not vis[cur]:\n",
    "                depths[cur] = depth\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "                minNode = min(minNode, cur)\n",
    "                # print('cur:', cur, depth, 'maxDepth:', maxDepth)\n",
    "                vis[cur] = True\n",
    "                newDepth = depth + 1\n",
    "                for n in graph[cur]:\n",
    "                    if not vis[n]:\n",
    "                        queue.append((n, newDepth))\n",
    "            head += 1\n",
    "\n",
    "        return minNode, maxDepth\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        time = [0] * n  # 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）\n",
    "        clock = 0\n",
    "        def bfs(start: int) -> int:  # 返回从 start 出发的最大深度\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:  # 没有在同一次 BFS 中访问过\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1  # 如果不是二分图（有奇环），则无法分组\n",
    "            # 否则一定可以分组\n",
    "            ans += max(bfs(x) for x in nodes)  # 枚举连通块的每个点，作为起点 BFS，求最大深度\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        time = [0] * n  # 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）\n",
    "        clock = 0\n",
    "        def bfs(start: int) -> int:  # 返回从 start 出发的最大深度\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:  # 没有在同一次 BFS 中访问过\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1  # 如果不是二分图（有奇环），则无法分组\n",
    "            # 否则一定可以分组\n",
    "            ans += max(bfs(x) for x in nodes)  # 枚举连通块的每个点，作为起点 BFS，求最大深度\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a - 1].append(b - 1)\n",
    "            graph[b - 1].append(a - 1)\n",
    "        colors = [0] * n \n",
    "        def bipartite(node, c):\n",
    "            colors[node] = c\n",
    "            nodes.append(node)\n",
    "            for nei in graph[node]:\n",
    "                if colors[nei] == c or (colors[nei] == 0 and not bipartite(nei, - c)):\n",
    "                    return False \n",
    "            return True \n",
    "        res = 0\n",
    "        time = 0\n",
    "        visit = [0] * n \n",
    "        for node in range(n):\n",
    "            if colors[node] != 0:\n",
    "                continue \n",
    "            nodes = []\n",
    "            if not bipartite(node, 1):\n",
    "                return - 1\n",
    "            curMax = 0\n",
    "            for cur in nodes:\n",
    "                queue = [cur]\n",
    "                depth = 0\n",
    "                time += 1 \n",
    "                visit[cur] = time \n",
    "                while queue:\n",
    "                    new = []\n",
    "                    for x in queue:\n",
    "                        for nei in graph[x]:\n",
    "                            if visit[nei] != time:\n",
    "                                new.append(nei)\n",
    "                                visit[nei] = time \n",
    "                    queue = new \n",
    "                    depth += 1 \n",
    "                curMax = max(curMax, depth)\n",
    "            res += curMax\n",
    "        return res \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        \n",
    "        time = [0] * n\n",
    "        clock = 0\n",
    "        def bfs(start):\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x, c):\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1\n",
    "            ans += max(bfs(x) for x in nodes)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a - 1].append(b - 1)\n",
    "            graph[b - 1].append(a - 1)\n",
    "        color = [0] * n \n",
    "        def bipatite(node, c):\n",
    "            nodes.append(node)\n",
    "            color[node] = c \n",
    "            for nei in graph[node]:\n",
    "                if color[nei] == c or (color[nei] == 0 and not bipatite(nei, - c)):\n",
    "                    return False \n",
    "            return True \n",
    "\n",
    "        res = 0\n",
    "        visit = [0] * n \n",
    "        time = 0\n",
    "        for node in range(n):\n",
    "            if color[node] != 0:\n",
    "                continue \n",
    "            nodes = []\n",
    "            if not bipatite(node, 1):\n",
    "                return - 1\n",
    "            curMax = 0\n",
    "            for start in nodes:\n",
    "                queue = [start]\n",
    "                time += 1\n",
    "                visit[start] = time \n",
    "                step = 0\n",
    "                while queue:\n",
    "                    new = []\n",
    "                    for cur in queue:\n",
    "                        for nei in graph[cur]:\n",
    "                            if visit[nei] != time:\n",
    "                                visit[nei] = time \n",
    "                                new.append(nei)\n",
    "                    queue = new \n",
    "                    step += 1 \n",
    "                curMax = max(curMax, step)\n",
    "            res += curMax\n",
    "        return res \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a - 1].append(b - 1)\n",
    "            graph[b - 1].append(a - 1)\n",
    "        color = [0] * n \n",
    "        def bipatite(node, c):\n",
    "            nodes.append(node)\n",
    "            color[node] = c \n",
    "            for nei in graph[node]:\n",
    "                if color[nei] == c or (color[nei] == 0 and not bipatite(nei, - c)):\n",
    "                    return False \n",
    "            return True \n",
    "\n",
    "        res = 0\n",
    "        visit = [0] * n \n",
    "        time = 0\n",
    "        for node in range(n):\n",
    "            if color[node] != 0:\n",
    "                continue \n",
    "            nodes = []\n",
    "            if not bipatite(node, 1):\n",
    "                return - 1\n",
    "            curMax = 0\n",
    "            for start in nodes:\n",
    "                queue = [start]\n",
    "                time += 1\n",
    "                visit[start] = time \n",
    "                step = 0\n",
    "                while queue:\n",
    "                    new = []\n",
    "                    for cur in queue:\n",
    "                        for nei in graph[cur]:\n",
    "                            if visit[nei] != time:\n",
    "                                visit[nei] = time \n",
    "                                new.append(nei)\n",
    "                    queue = new \n",
    "                    step += 1 \n",
    "                curMax = max(curMax, step)\n",
    "            res += curMax\n",
    "        return res \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "\n",
    "        color = [0]*n\n",
    "        def erfentu(x,c):\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or (color[y] == 0 and not erfentu(y, -c)):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        visited = [0]*n #表明每个节点所属块\n",
    "        clock = 0\n",
    "        def bfs(start):\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            visited[start] = clock\n",
    "            queue = collections.deque()\n",
    "            queue.append(start)\n",
    "            while queue:\n",
    "                size = len(queue)\n",
    "                for _ in range(size):\n",
    "                    x = queue.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if visited[y] != clock:\n",
    "                            visited[y] = clock\n",
    "                            queue.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        ans = 0\n",
    "        for i,c in enumerate(color):\n",
    "            if c: continue\n",
    "            else:\n",
    "                nodes = []\n",
    "                if not erfentu(i, 1):\n",
    "                    return -1\n",
    "                # tmp = 0\n",
    "                # for x in nodes:\n",
    "                #     tmp = max(tmp,bfs(x))\n",
    "                # ans += tmp\n",
    "                ans += max(bfs(x) for x in nodes)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        time = [0] * n  # 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）\n",
    "        clock = 0\n",
    "        def bfs(start: int) -> int:  # 返回从 start 出发的最大深度\n",
    "            depth = 0\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            time[start] = clock\n",
    "            q = [start]\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if time[y] != clock:  # 没有在同一次 BFS 中访问过\n",
    "                            time[y] = clock\n",
    "                            q.append(y)\n",
    "                depth += 1\n",
    "            return depth\n",
    "\n",
    "        color = [0] * n\n",
    "        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解\n",
    "            nodes.append(x)\n",
    "            color[x] = c\n",
    "            for y in g[x]:\n",
    "                if color[y] == c or color[y] == 0 and not is_bipartite(y, -c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i, c in enumerate(color):\n",
    "            if c: continue\n",
    "            nodes = []\n",
    "            if not is_bipartite(i, 1): return -1  # 如果不是二分图（有奇环），则无法分组\n",
    "            # 否则一定可以分组\n",
    "            ans += max(bfs(x) for x in nodes)  # 枚举连通块的每个点，作为起点 BFS，求最大深度\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "                \n",
    "        vis = [0] * (n+1)\n",
    "        edgevis = set()\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            if vis[i]:continue\n",
    "            F = [0 for i in range(n+1)]\n",
    "            T = []\n",
    "            S = set()\n",
    "            st = [i]\n",
    "            cnt = 0\n",
    "            while st:\n",
    "                temp = st\n",
    "                st = []\n",
    "                while temp:\n",
    "                    o = temp.pop()\n",
    "                    for nxt in G[o]:\n",
    "                        if (nxt,o) in edgevis or (o,nxt) in edgevis:\n",
    "                            if F[o] != cnt and not (cnt + F[nxt]) % 2:return -1\n",
    "                            continue\n",
    "                        edgevis.add((o,nxt))\n",
    "                        st.append(nxt)\n",
    "                    vis[o] = 1\n",
    "                    if o not in S:\n",
    "                        S.add(o)\n",
    "                        T.append(o)\n",
    "                    F[o] = cnt\n",
    "                cnt += 1\n",
    "            tempres = 0\n",
    "            for j in T:\n",
    "                v = [0] * (n+1)\n",
    "                st = [j]\n",
    "                v[j] = 1\n",
    "                cnt = 0\n",
    "                while st:\n",
    "                    temp = st\n",
    "                    st = []\n",
    "                    while temp:\n",
    "                        o = temp.pop()\n",
    "                        for nxt in G[o]:\n",
    "                            if v[nxt]:continue\n",
    "                            v[nxt] = 1\n",
    "                            st.append(nxt)\n",
    "                    cnt += 1\n",
    "                tempres = max(tempres,cnt)\n",
    "            res += tempres\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        colors = [0] * n\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            adj[a - 1].append(b - 1)\n",
    "            adj[b - 1].append(a - 1)\n",
    "        \n",
    "        subgraph = []\n",
    "\n",
    "        def solve(start):\n",
    "            subgraph.clear()\n",
    "            que = deque([(start, 1)])\n",
    "            while len(que) > 0:\n",
    "                cur, color = que.pop()\n",
    "                if colors[cur] == 0:\n",
    "                    colors[cur] = color\n",
    "                    subgraph.append(cur)\n",
    "                    new_color = -color\n",
    "                    for nxt in adj[cur]:\n",
    "                        que.appendleft((nxt, new_color))\n",
    "                else:\n",
    "                    if colors[cur] != color:\n",
    "                        return -1\n",
    "            \n",
    "            def bfs(node):\n",
    "                visited = [False] * n\n",
    "                visited[node] = True\n",
    "                turn = 0\n",
    "                cur_turn = [node]\n",
    "                while len(cur_turn) > 0:\n",
    "                    turn += 1\n",
    "                    new_turn = []\n",
    "                    for no in cur_turn:\n",
    "                        for nxt in adj[no]:\n",
    "                            if not visited[nxt]:\n",
    "                                visited[nxt] = True\n",
    "                                new_turn.append(nxt)\n",
    "                    cur_turn = new_turn\n",
    "                return turn\n",
    "\n",
    "            cur = 0\n",
    "            for node in subgraph:\n",
    "                cur = max(cur, bfs(node))\n",
    "\n",
    "            return cur\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if colors[i] == 0:\n",
    "                cur = solve(i)\n",
    "                if cur == -1:\n",
    "                    return -1\n",
    "                ans += cur\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
